//AVL tree (with left-right = 1 balance condition)


#include "stdio.h"
#include "stdlib.h"
#include "math.h"


typedef int elementType;

struct TreeNode
{
	elementType element;
	int height;
	struct TreeNode *left, *right;
};

typedef struct TreeNode *binarytree;
typedef struct TreeNode *position;



void makeEmpty(binarytree t)
{
	if(t){	
		makeEmpty(t->left);
		makeEmpty(t->right);
		free(t);
	}	
}


position findRightMostNode(binarytree t)
{
	if(t != NULL)
		while(t->right != NULL)	
			t = t->right;
	
	return t;
}



//Preorder : root first
void preorder(binarytree t, int level)
{
	int i;

	if(t){
		for(i=0; i<level; i++, printf(" "));
		printf("%d\n", t->element);
		preorder(t->left, level+1);		
		preorder(t->right, level+1);
	}
 }


//right - root - left
void postorder(binarytree t, int *pvalue, int *plevel)
{
	
	if(t->left != NULL)
		postorder(t->left, pvalue, plevel);
	
	printf("got v:%d  l:%d\n", *pvalue, *plevel);
	
	*pvalue = *pvalue * 10 + t->element;
	printf("set v:%d  l:%d e:%d\n", *pvalue, *plevel, t->element);

	(*plevel)++;
	
	if(t->right != NULL){
		postorder(t->right, pvalue, plevel);
		(*plevel)++;
	}

		printf("v:%d  l:%d\n", *pvalue, *plevel);
	
 }


//Returns the new tree root, not inserted position
binarytree insertT(binarytree t, elementType x)
{
	if(t == NULL){
		t = (binarytree)malloc(sizeof(struct TreeNode));
		if(t){
			t->element = x;
			t->height = 0;  //empty tree has ht = -1
			t->left = t->right = NULL;			
		}
		else
			printf("Out of space");
		
	}
	else if(x < t->element){
		t->left = insertT(t->left, x);	//insert at left subtree potentially increasing its height		
	}
	else if(x > t->element){
		t->right = insertT(t->right, x);			//insert at right subtree potentially increasing its height		
	}
	
	
	return t; // return same tree as we got, x is in one of its subtrees(or was inserted there)
		
}



int main(int argc, char* argv[])
{
	binarytree t=NULL;
	

/*	for(i=0; i<5; i++){

		printf("Insert %d:\n", i);
		t = insertT(t, i);
		preorder(t, 0);
		printf("--------\n");
	}
*/

		t = insertT(t, 2);
		t = insertT(t, 1);
		t = insertT(t, 3);
		preorder(t, 0);

	int value =0, level=0;
	postorder(t, &value, &level);

	printf("value = %d\n", value);

	
			
	return 0;
}

